import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-10-20
 * Time:20:39
 */
public class TestDemo {
    public static void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;
            for ( ; j >= 0; j--) {
                if (tmp < array[j]){
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }
    public static void shell(int[] array,int gap){
        for (int i = gap; i <array.length ; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0 ; j -= gap) {
                if (tmp < array[j]){
                    array[j + gap] = array[j];
                }else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }
    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i ; j < array.length; j++) {
                if (array[j] < array[min]){
                    min = j;
                }
            }
            swap(array,i,min);
        }
    }

    public static void heapSort(int[] array){
        //将大堆
        creatBigHeap(array);
        //交换堆顶与堆尾的位置
        for (int i = array.length - 1; i > 0 ; i--) {
            swap(array,0, i);
            //交换之后，再次调整为大堆
            shiftDown(array,0,i);
        }
    }
    //由于是升序建大堆
    private static void creatBigHeap(int[] array) {
        for (int parent = (array.length - 1) / 2; parent >= 0 ; parent--) {
            shiftDown(array,parent, array.length - 1);
        }
    }
//向下调整算法
    private static void shiftDown(int[] array, int parent,int len) {
        int child = 2 * parent + 1;//默认为左孩子
        while (child < len){
            if (child + 1 < len && array[child]  < array[child + 1]){
                child++;
            }

            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    public static void bubbleSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = 1; j < array.length - i ; j++) {
                if (array[j - 1] > array[j]){
                    swap(array,j - 1, j);
                }
            }
        }
    }

    public static void medianOfThree(int[] array,int left,int right){
        int mid = (left + right) / 2;

        if (array[mid] >array[left]){
            swap(array,mid,left);
        }// array[mid] <= array[left];

        if (array[right] < array[left]){
            swap(array,left,right);
        }// array[left] <= array[right];

        if (array[left] < array[mid]){
            swap(array,mid,left);
        }
    }
    public static void quickSort(int[] array,int left,int right){

        if (left >= right){
            return;
        }

        if (right - left < 100){
            insertSort1(array,left,right);
        }
//        medianOfThree(array,left,right);
        int piovt = partition(array,left,right);
        quickSort(array,left,piovt - 1);
        quickSort(array,piovt + 1, right);
    }

    private static void insertSort1(int[] array,int left,int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left ; j--) {
                if (array[j] > tmp){
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right){
            while (array[right] >= tmp && left < right){
                right--;
            }
            array[left] = array[right];
            while (array[left] <= tmp && left < right){
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    private static int partition1(int[] array, int left, int right) {
        int tmp = array[left];
        int start = left;
        while (left < right){
            while (array[right] >= tmp && left < right){
                right--;
            }
            while (array[left] <= tmp && left < right){
                left++;
            }
            swap(array,left,right);
        }
        swap(array,start,right);
        return right;
    }
    public static void quickSortNor(int[] array){
        Stack<Integer> stack = new Stack<>();
        stack.push(array.length - 1);
        stack.push(0);
        while (!stack.isEmpty()){
            int left = stack.pop();
            int right = stack.pop();
            if (left >= right){
                continue;
            }

            int pivot = partition(array,left,right);
            stack.push(pivot - 1);
            stack.push(left);
            stack.push(right);
            stack.push(pivot + 1);
        }
    }
    public static void quickSortNor1(int[] array){
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        stack.push(array.length - 1);
        while (!stack.isEmpty()) {
            int right = stack.pop();
            int left = stack.pop();
            if (left >= right){
                continue;
            }
            int pivot = partition(array, left, right);
            if (pivot > left + 1) {
                stack.push(left);
                stack.push(pivot - 1);
            }

            if (pivot < right - 1) {
                stack.push(pivot + 1);
                stack.push(right);
            }
        }
    }
    public static int[] mergeArray(int[] array1,int[] array2){
        int left1 = 0;
        int left2 = 0;
        int right1 = array1.length ;
        int right2 = array2.length ;
        int i = 0;
        int[] tmp = new int[array1.length + array2.length];
        while (left1 < right1 && left2 < right2){
            if (array1[left1] < array2[left2]){
                tmp[i++] = array1[left1++];
            }else {
                tmp[i++] = array2[left2++];
            }
        }
        while (left1 < right1){
            tmp[i++] = array1[left1++];
        }

        while (left2 < right2){
            tmp[i++] = array2[left2++];
        }
        return tmp;
    }

    public static void main3(String[] args) {
        int[] array1 = {1,3,5,7,8};
        int[] array2 = {0,2,4,6,9};
        int[] tmp = mergeArray(array1,array2);
        System.out.println(Arrays.toString(tmp));
    }
    /*
归并排序
时间复杂度：O(n*logn)
空间复杂度：O(n)
稳定性：稳定
 */
    public static void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length - 1);
    }

    public static void mergeSortInternal(int[] array, int left, int right) {
        if (left >= right){
            return;
        }

        int mid = (left + right) / 2;
        mergeSortInternal(array,left,mid);
        mergeSortInternal(array,mid + 1, right);

        merge(array,left,right,mid);
    }
    public static void mergeSort1(int[] array){
        int gap = 1;
        for (int i = gap; i < array.length; i *= 2) {
            merge1(array,i);
        }
    }
    public static void merge1(int[] array,int gap){

         int s1 = 0;
         int e1 = s1 + gap - 1;
         int s2 = e1 + 1;
         int e2 = s2 + gap -1 >= array.length - 1? array.length - 1: s2 + gap - 1;
         int[] tmp = new int[array.length];
         int k = 0;
         //至少有两段
         while (s2 < array.length){
             while (s1 <= e1 && s2 <= e2){
                 if (array[s1] < array[s2]){
                   tmp[k++] = array[s1++];
                 }else {
                     tmp[k++] = array[s2++];
                 }
             }

             while (s1 <= e1){
                 tmp[k++] = array[s1++];
             }

             while (s2 <= e2){
                 tmp[k++] = array[s2++];
             }

             s1 = e2 + 1;
             e1 = s1 + gap - 1;
             s2 = e1 + 1;
             e2 = s2 + gap -1 >= array.length - 1? array.length - 1: s2 + gap - 1;
         }
         //只有一段
        while (s1 <= array.length -1){
            tmp[k++] = array[s1++];
        }

        for (int i = 0; i < k; i++) {
            array[i] = tmp[i];
        }

    }
    public static void merge(int[] array, int left, int right, int mid) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        int  k = 0;
        int[] tmp = new int[right - left + 1];
        while (s1 <= s2 && s2 <= e2) {
            if (array[s1] < array[s2]){
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmp[k++] = array[s1++];
        }

        while (s2 <= e2){
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < k; i++) {
            //排好序的数放到合适的位置
            array[i + left] = tmp[i];
        }
    }

    public static void mergeSort2(int[] array){
        mergeSortInternal2(array,0,array.length -1);
    }

    private static void mergeSortInternal2(int[] array, int left, int right) {
        if (left>=right){
            return;
        }
        int mid = (left + right) / 2;
        //分为长度为1的区间
        mergeSortInternal2(array,left,mid);
        mergeSortInternal2(array,mid + 1, right);

        int[] tmp = new int[right - left + 1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        // 合并
        while (s1 <= e1 && s2 <= e2){
            if (array[s1] < array[s2]){
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }

        while (s1 <= e1){
            tmp[k++] = array[s1++];
        }

        while (s2 <= e2){
            tmp[k++] = array[s2++];
        }

        for (int i = 0; i < k; i++) {
            array[left + i] = tmp[i];
        }
    }

    public static void main1(String[] args) {
        long  start = System.currentTimeMillis();
        Random random = new Random(10_0000);
        int[] array = new int[10_0000];
        //数组为有序数组
//        for (int i = 0; i < array.length; i++) {
//            array[i] = i;
//        }
        // 数组为无序数组
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt();
        }
        //排序算法
        quickSort(array,0,array.length - 1);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    public static void mergeSortNor(int[] array){
        int gap = 1;
        for (int i = gap; i < array.length; i *= 2) {
            merge2(array,i);
        }
    }

    private static void merge2(int[] array, int gap) {

        int s1 = 0;
        int e1 = s1 + gap - 1;
        int s2 = e1 + 1;
        int e2 = (s2 + gap - 1 >= array.length - 1)? (array.length - 1) : (s2 + gap - 1);
        int[] tmp = new int[array.length];
        int k = 0;
        //当有两个子序列时
        while (s2 < array.length){
            while (s1 <= e1 && s2 <= e2){
                if (array[s1] < array[s2]){
                    tmp[k++] = array[s1++];
                }else {
                    tmp[k++] = array[s2++];
                }
            }

            while (s1 <= e1){
                tmp[k++] = array[s1++];
            }

            while (s2 <= e2){
                tmp[k++] = array[s2++];
            }

            s1 = e2 + 1;
            e1 = s1 + gap - 1;
            s2 = e1 + 1;
            e2 = (s2 + gap - 1 >= array.length - 1)? (array.length - 1) : (s2 + gap - 1);
        }
        //当只有一个序列时
        while (s1 <= array.length - 1){
            tmp[k++] = array[s1++];
        }

        for (int i = 0; i < k; i++) {
            array[i] = tmp[i];
        }

    }

    public static void main(String[] args) {
        int[] array = {2,9,7,4,1,8,0,5,3,6};
        System.out.println("排序前:" + Arrays.toString(array));
        //排序算法
//        selectSort(array);
//        heapSort(array);
//        bubbleSort(array);
//        quickSort(array,0,array.length - 1);
//        quickSortNor(array);
//        quickSortNor1(array);
//        mergeSort(array);
//        mergeSort1(array);
//        mergeSort2(array);
        mergeSortNor(array);
        System.out.println("排序后:" + Arrays.toString(array));
    }
}
